The present invention relates to a digital image quantization apparatus; and more particularly, to an apparatus for quantizing a digital image of black and white mode by using an error diffusion coefficient and threshold modulation in zigzag quantization.
Typically, an analog image is converted to a digital image through sampling and quantization. That is, the digital image has gray scale value quantized based on the reflectivity of light within the sampling region. For example, when the gray scale value is quantized to one of 256 steps between white and black in case of a black and white mode digital image, the digital image can represent 254 scales of gray as well as black and white. Such a digital image is displayed on a monitor or outputted by an image output device such as a laser print, an inkjet printer and a digital copying machine, after digital image processing depending on its object.
On the other hand, most image output device prints a number of a certain size of pixels in a lattice on a white paper sheet. That is, the image output device can represent one of the white color of the paper sheet and ink or toner color.
When the input image to be printed is a continuous gray scale image, the input image is converted to a quantized image before printing and the converted quantized image is printed by the output device. The technique for converting the continuous gray scale to the quantized image is referred to xe2x80x98image halftoningxe2x80x99. For a black and white mode output device, the printed black pixels within a given region are not recognized as separated pixels but as an averaged gray color when it is viewed from the distance. It is an illusion due to a limit of resolution of eyes of human being. Accordingly, the picture quality of the printed image depends on the image halftoning used in the quantization.
Oh the other hand, during a number of image halftoning techniques, there are two most popular methods, a dithering method and an error diffusion method. The dithering method quantizes the gray scale of the pixel by using a predetermined threshold sequence. The error diffusion method diffuses a quantization error of a current pixel into its adjacent pixels such that the quantization error is accounted for the quantization of the adjacent pixels. The dithering method is often used for its fast speed. The error diffusion method is used for its high quality of the quantized output image.
The error diffusion method was discussed at first in xe2x80x9cAn adaptive algorithm for spatial gray scalexe2x80x9d, Floyd and Steinberg, Society For Information Display(SID) international symposium proceeding, 1975. The method of Floyd and Steinberg is expressed as follows:
e(m,n)=u(m,n)xe2x88x92b(m,n)xe2x80x83xe2x80x83(1)
where e(m,n) is the error value of the quantized output image, u(m,n) is the updated pixel value of the current input pixel, which is updated by using the diffused error from the previous pixel, and b(m,n) is the (m,n)-th pixel of the quantized output image, which has one of xe2x80x980xe2x80x99 and xe2x80x98255xe2x80x99.
And, in the equation (1), if u(m,n) greater than t(m,n), then b(m,n)=255 (where t(m,n) is a predetermined threshold xe2x80x98127xe2x80x99 regardless of (m,n)) and, if otherwise, then b(m,n)=0.                               u          ⁡                      (                          m              ,              n                        )                          =                              i            ⁡                          (                              m                ,                n                            )                                +                                    ∑                              k                ,                                  l                  ∈                  R                                                      ⁢                          xe2x80x83                        ⁢                                          w                ⁡                                  (                                      k                    ,                    l                                    )                                            ⁢                              e                ⁡                                  (                                                            m                      -                      k                                        ,                                          n                      -                      l                                                        )                                                                                        (        2        )            
where i(m,n) is the (m,n)-th pixel of the given input continuous gray scale image and has its value between 0 to 255, R is a set of the adjacent pixels to which the quantization error is to be diffused, and w(k,l) is the weight of the quantization error to be diffused into the (k,l)-th pixels in R, k and l being positive integers.
However, the error diffusion method as described above results in artifacts with specific dot alignment which will be recognized by eyesight of human being. There are two representative artifacts, fingerprint and worm artifacts. The fingerprint artifact is a fingerprint-like regular pattern that appears mostly in mid-level gray scale, and can be eliminated substantially with higher resolution of the output device. In contrast, the worm artifact is a pattern that appears in the bright region and dark region due to recognizable orientation of the dots and is leaved unsolved, that is, recognizable, even when the higher resolution of the output device.
It is, therefore, a primary object of the invention to provide an apparatus for modulating a threshold to be used in quantization of an updated input pixel by using an error diffusion coefficient in digital image quantization with zigzag quantization order to distribute dots evenly in bright region and dark region of an image.
In accordance with one aspect of the present invention, there is provided an apparatus for quantizing an original digital image having a certain number of gray scales to a second image having a fewer number of gray scales than that of the original digital image, comprising: updating means for updating an input pixel value using update of a current input pixel from the original digital image by using information for the input pixel; quantizing means for quantizing the updated pixel value from the updating means by using a predetermined threshold to output the output image of the quantized pixel value; quantization error detecting means for detecting an error value of the output image of the quantized pixel value received from the quantizing means by using the updated input pixel value from the updating means; threshold modulating means for modulating the threshold of the quantizing means based on the input pixel value and the output image of the quantized pixel value from the quantizing means; and diffussing means for diffusing the quantization error value of the quantized pixel value of the current input pixel received from the quantization error detecting means into adjacent pixels of the current input pixel to apply the update information for the adjacent input pixel of the current input pixel to the updating means based the quantization error of the current pixel and a predetermined error diffusion coefficient, wherein the predetermined error diffusion coefficient is determined by a matrix:       [                                        w            ⁢                          xe2x80x83                        ⁢                          (                              2                ,                1                            )                                                            w            ⁢                          xe2x80x83                        ⁢                          (                              2                ,                0                            )                                                                        w            ⁢                          xe2x80x83                        ⁢                          (                              1                ,                1                            )                                                            w            ⁢                          xe2x80x83                        ⁢                          (                              1                ,                0                            )                                                                        w            ⁢                          xe2x80x83                        ⁢                          (                              0                ,                1                            )                                                            xe2x80x83                                ]    =      [                                        2            /            16                                                3            /            16                                                            3            /            16                                                4            /            16                                                            4            /            16                                    *                      ]  
where xcfx89(2,1), xcfx89(2,0), xcfx89(1,1), xcfx89(0,1) and xcfx89(0,1) are weights of the error diffusion.
In accordance with one aspect of the present invention, there is provided a threshold modulation method for quantizing an original digital image having a certain number of gray scales to a second image having a fewer number of gray scales than that of the original digital image, comprising the steps of: a) determining whether an input pixel value is greater than a threshold of a current input pixel from the original digital image; b) determining whether an output image value is a predetermined high level or low level based on the threshold; c) if the input pixel value is greater than the threshold and the output image value is the predetermined high level, modulating the threshold of the adjacent pixel as:
t(m+p, n+q)xe2x88x92=Tf1(p,q)xc3x97t(m,n),
wherein t(m,n) is the threshold of the (m,n)-th pixel being the current input pixel, t(m+p, n+q) is the threshold of the pixel separated from the (m,n)-th pixel by (p,q), and Tf1(p,q) is a first threshold modulation coefficient; d) if the input pixel value is greater than the threshold and the output image value is the predetermined low level, modulating the threshold of the adjacent pixel as:
t(m+p, n+q)+=Tf2,
wherein t(m,n) is the threshold of the (m,n)-th pixel being current input pixel, t(m+p, n+q) is the threshold of the pixel separated from the (m,n)-th pixel by (p,q), and Tf2 is a second threshold modulation coefficient; e) if the input pixel value is not greater than the threshold and the output image value is the predetermined low level, modulating the threshold of the adjacent pixel as:
t(m+p, n+q)xe2x88x92=Tf1(p,q)xc3x97t(m,n),
wherein t(m,n) is the threshold of the (m,n)-th pixel being the current input pixel, t(m+p, n+q) is the threshold of the pixel separated from the (m,n)th pixel by (p,q), and Tf1(p,q) is a first threshold modulation coefficient; and f) if the input pixel value is not greater than the threshold and the output image value is the predetermined high level, modulating the threshold of the adjacent pixel as:
t(m+p, n+q)xe2x88x92=Tf2,
wherein t(m,n) is the threshold of the (m,n)th pixel being the currently input pixel, t(m+p, n+q) is the threshold of the pixel separated from the (m,n)th pixel by (p,q), and Tf2 is a second threshold modulation coefficient.